1. Field of the Invention
This invention relates to the allocation of channels to radio transceivers in a radio network. The described embodiments are directed to the fixed base stations of a cellular telephone network, but the invention may also find application in other networks of radio transmitters and/or receivers.
2. Related Art
A cellular telephone network consists of a number of fixed base station transceivers and a much larger number of mobile handsets which communicate with base stations via a radio channel. The ‘cells’ from which cellular telephone networks get their name are the coverage areas of the individual fixed radio base stations. Each operator is permitted to use a limited number of radio channels, and there are not enough such channels for each phone call in the network to be carried on a different channel. Thus a central principle of such networks is channel re-use: at any time many base stations may be operating on each channel. This introduces the possibility of interference between phone calls. Interference from other calls using the same channel is known as ‘co-channel interference’. ‘Adjacent channel’ interference, due to another call using a different channel, is also a problem: a call made on a channel corresponding to a frequency band of 4000-4025 kHz is liable to interference from a call on the adjacent band; 4025-4050 kHz. Adjacent channel interference can occur between two calls in the same cell, as well as between adjacent cells.
The problem facing the network operator is to allocate channels to base stations such that demand for channels across the network is met, while keeping interference within acceptable levels. These aims are clearly in conflict: if more channels are allocated to each base station, then each channel must be used by more base stations, and so it is harder to plan to avoid unacceptable interference.
An added difficulty is that the demand across the network is neither uniform nor static. Some cells will experience high demand at particular times of the day but lower than average demand for the rest of the day, for example cells through which major arteries of commuter traffic pass. Even worse, for efficient channel allocation, are the unpredictable fluctuations in demand resulting from events such as road congestion, disruptions to train services, or events attracting the attention of the news media.
It is currently common practice for operators to use a fixed channel allocation plan. The channels used by any particular base station are determined by a “frequency plan”. This plan is modified periodically to meet quality of service criteria, for example to meet changes in demand, and to allow for the installation of new base stations. During the existence of one frequency plan, each base station has its own allocation of channels, which remains the same throughout the life of the plan, which is typically several months.
The applicant already has an International patent Application (WO99/56488) which discloses a method for channel allocation in which each base station is an autonomous negotiating unit. Each base station transceiver has a preference value (between 0 and 1) for each of the channels available to the overall channel allocation plan. The base station adjusts its preference values for each channel on the basis of its neighbours' preferences for the same channel. The greater its neighbours' preference for a channel, the greater the reduction in that base station's preference for the same channel. Initially all base stations have approximately the same preference for all channels but, over time, heterogeneity emerges, and is magnified by inhibitory feedback between cells. A particular base station eventually has significant preferences for certain channels, but its preference for all other channels will be low due to inhibition from neighbours.
At any time this heterogeneous set of preferences can be turned into a viable channel allocation plan by applying an algorithm which takes the highest preference channels in each base station and allocates them to that base station for actual use in communicating with handsets.
During the process, in each base station the adjustment to each preference for each channel is proportional to the inhibition from all neighbours. Inhibition is calculated as follows: for each neighbour the preference of that neighbour for the same channel is multiplied by a coefficient obtained from a look-up table representing the strength of potential interference from that neighbour (i.e. the degree of co-channel interference which would result if the base station and this neighbour actually used the same channel to communicate with their handsets). For near neighbours this coefficient will generally be high whilst for distant neighbours it will be low. There may be exceptions in which a geographically distant neighbour is able (due to some quirk of the terrain and the properties of radio wave propagation) to interfere strongly. This would be reflected in a high coefficient. Conversely, local topography may inhibit interference between geographically close neighbours. The total inhibition experienced is simply the sum of all the inhibitions calculated for all neighbours on the channel in question.
The values assigned to the coefficients are important for the quality of the channel allocation produced by this method. If a coefficient is not an accurate reflection of the strength of inhibition from the neighbour to the base station, then when the channels are allocated and used in a real system there is likely to be higher interference than expected. This is a common problem with optimisation techniques: the quality of the solutions depend on how accurately the search space represents the reality in which the solution must perform.
The process of compiling the look-up table requires a mobile monitoring unit (a “man in a van”) to measure signal strength at various positions in the network. The attenuation of a signal from that base station to the monitor's position can then be calculated from the signal strength measured by the monitoring unit. This work is time consuming. It is preferably carried out at times of low traffic (e.g. middle of the night) so that a base station can devote itself to transmitting test signals of known power. If test signals are used which are not part of that base station's current frequency allocation they may interfere with signals from other nearby base stations. Moreover, even if a highly accurate table has been produced it only remains accurate until changes are made to the network. If a new base station is constructed the table is outdated. Changes in local topography, such as the construction or demolition of buildings, seasonal effects such as whether trees are in leaf, or even a change in the weather, can also affect the accuracy of a table painstakingly constructed under the previous conditions.